/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.lucene.util.packed;

import java.io.IOException;
import java.util.Arrays;
import org.apache.lucene.store.DataInput;
import org.apache.lucene.store.DataOutput;
import org.apache.lucene.util.Accountable;
import org.apache.lucene.util.LongsRef;
import org.apache.lucene.util.RamUsageEstimator;

/**
 * Simplistic compression for array of unsigned long values. Each value is {@code >= 0} and {@code
 * <=} a specified maximum value. The values are stored as packed ints, with each value consuming a
 * fixed number of bits.
 *
 * @lucene.internal
 */
public class PackedInts {

  /** At most 700% memory overhead, always select a direct implementation. */
  public static final float FASTEST = 7f;

  /** At most 50% memory overhead, always select a reasonably fast implementation. */
  public static final float FAST = 0.5f;

  /** At most 25% memory overhead. */
  public static final float DEFAULT = 0.25f;

  /** No memory overhead at all, but the returned implementation may be slow. */
  public static final float COMPACT = 0f;

  /** Default amount of memory to use for bulk operations. */
  public static final int DEFAULT_BUFFER_SIZE = 1024; // 1K

  public static final String CODEC_NAME = "PackedInts";
  public static final int VERSION_MONOTONIC_WITHOUT_ZIGZAG = 2;
  public static final int VERSION_START = VERSION_MONOTONIC_WITHOUT_ZIGZAG;
  public static final int VERSION_CURRENT = VERSION_MONOTONIC_WITHOUT_ZIGZAG;

  /** Check the validity of a version number. */
  public static void checkVersion(int version) {
    if (version < VERSION_START) {
      throw new IllegalArgumentException(
          "Version is too old, should be at least " + VERSION_START + " (got " + version + ")");
    } else if (version > VERSION_CURRENT) {
      throw new IllegalArgumentException(
          "Version is too new, should be at most " + VERSION_CURRENT + " (got " + version + ")");
    }
  }

  /**
   * A format to write packed ints.
   *
   * @lucene.internal
   */
  public enum Format {
    /** Compact format, all bits are written contiguously. */
    PACKED(0) {

      @Override
      public long byteCount(int packedIntsVersion, int valueCount, int bitsPerValue) {
        return (long) Math.ceil((double) valueCount * bitsPerValue / 8);
      }
    },

    /**
     * A format that may insert padding bits to improve encoding and decoding speed. Since this
     * format doesn't support all possible bits per value, you should never use it directly, but
     * rather use {@link PackedInts#fastestFormatAndBits(int, int, float)} to find the format that
     * best suits your needs.
     *
     * @deprecated Use {@link #PACKED} instead.
     */
    @Deprecated
    PACKED_SINGLE_BLOCK(1) {

      @Override
      public int longCount(int packedIntsVersion, int valueCount, int bitsPerValue) {
        final int valuesPerBlock = 64 / bitsPerValue;
        return (int) Math.ceil((double) valueCount / valuesPerBlock);
      }

      @Override
      public boolean isSupported(int bitsPerValue) {
        return Packed64SingleBlock.isSupported(bitsPerValue);
      }

      @Override
      public float overheadPerValue(int bitsPerValue) {
        assert isSupported(bitsPerValue);
        final int valuesPerBlock = 64 / bitsPerValue;
        final int overhead = 64 % bitsPerValue;
        return (float) overhead / valuesPerBlock;
      }
    };

    /** Get a format according to its ID. */
    public static Format byId(int id) {
      for (Format format : Format.values()) {
        if (format.getId() == id) {
          return format;
        }
      }
      throw new IllegalArgumentException("Unknown format id: " + id);
    }

    Format(int id) {
      this.id = id;
    }

    public final int id;

    /** Returns the ID of the format. */
    public int getId() {
      return id;
    }

    /**
     * Computes how many byte blocks are needed to store <code>values</code> values of size <code>
     * bitsPerValue</code>.
     */
    public long byteCount(int packedIntsVersion, int valueCount, int bitsPerValue) {
      assert bitsPerValue >= 0 && bitsPerValue <= 64 : bitsPerValue;
      // assume long-aligned
      return 8L * longCount(packedIntsVersion, valueCount, bitsPerValue);
    }

    /**
     * Computes how many long blocks are needed to store <code>values</code> values of size <code>
     * bitsPerValue</code>.
     */
    public int longCount(int packedIntsVersion, int valueCount, int bitsPerValue) {
      assert bitsPerValue >= 0 && bitsPerValue <= 64 : bitsPerValue;
      final long byteCount = byteCount(packedIntsVersion, valueCount, bitsPerValue);
      assert byteCount < 8L * Integer.MAX_VALUE;
      return (int) ((byteCount + 7) >>> 3);
    }

    /** Tests whether the provided number of bits per value is supported by the format. */
    public boolean isSupported(int bitsPerValue) {
      return bitsPerValue >= 1 && bitsPerValue <= 64;
    }

    /** Returns the overhead per value, in bits. */
    public float overheadPerValue(int bitsPerValue) {
      assert isSupported(bitsPerValue);
      return 0f;
    }

    /** Returns the overhead ratio (<code>overhead per value / bits per value</code>). */
    public final float overheadRatio(int bitsPerValue) {
      assert isSupported(bitsPerValue);
      return overheadPerValue(bitsPerValue) / bitsPerValue;
    }
  }

  /** Simple class that holds a format and a number of bits per value. */
  public record FormatAndBits(Format format, int bitsPerValue) {}

  /**
   * Try to find the {@link Format} and number of bits per value that would restore from disk the
   * fastest reader whose overhead is less than <code>acceptableOverheadRatio</code>.
   *
   * <p>The <code>acceptableOverheadRatio</code> parameter makes sense for random-access {@link
   * Reader}s. In case you only plan to perform sequential access on this stream later on, you
   * should probably use {@link PackedInts#COMPACT}.
   *
   * <p>If you don't know how many values you are going to write, use <code>valueCount = -1</code>.
   */
  public static FormatAndBits fastestFormatAndBits(
      int valueCount, int bitsPerValue, float acceptableOverheadRatio) {
    if (valueCount == -1) {
      valueCount = Integer.MAX_VALUE;
    }

    acceptableOverheadRatio = Math.max(COMPACT, acceptableOverheadRatio);
    acceptableOverheadRatio = Math.min(FASTEST, acceptableOverheadRatio);
    float acceptableOverheadPerValue = acceptableOverheadRatio * bitsPerValue; // in bits

    int maxBitsPerValue = bitsPerValue + (int) acceptableOverheadPerValue;

    int actualBitsPerValue = -1;

    // rounded number of bits per value are usually the fastest
    if (bitsPerValue <= 8 && maxBitsPerValue >= 8) {
      actualBitsPerValue = 8;
    } else if (bitsPerValue <= 16 && maxBitsPerValue >= 16) {
      actualBitsPerValue = 16;
    } else if (bitsPerValue <= 32 && maxBitsPerValue >= 32) {
      actualBitsPerValue = 32;
    } else if (bitsPerValue <= 64 && maxBitsPerValue >= 64) {
      actualBitsPerValue = 64;
    } else {
      actualBitsPerValue = bitsPerValue;
    }

    return new FormatAndBits(Format.PACKED, actualBitsPerValue);
  }

  /** A decoder for packed integers. */
  public interface Decoder {

    /**
     * The minimum number of long blocks to encode in a single iteration, when using long encoding.
     */
    int longBlockCount();

    /** The number of values that can be stored in {@link #longBlockCount()} long blocks. */
    int longValueCount();

    /**
     * The minimum number of byte blocks to encode in a single iteration, when using byte encoding.
     */
    int byteBlockCount();

    /** The number of values that can be stored in {@link #byteBlockCount()} byte blocks. */
    int byteValueCount();

    /**
     * Read <code>iterations * blockCount()</code> blocks from <code>blocks</code>, decode them and
     * write <code>iterations * valueCount()</code> values into <code>values</code>.
     *
     * @param blocks the long blocks that hold packed integer values
     * @param blocksOffset the offset where to start reading blocks
     * @param values the values buffer
     * @param valuesOffset the offset where to start writing values
     * @param iterations controls how much data to decode
     */
    void decode(long[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations);

    /**
     * Read <code>8 * iterations * blockCount()</code> blocks from <code>blocks</code>, decode them
     * and write <code>iterations * valueCount()</code> values into <code>values</code>.
     *
     * @param blocks the long blocks that hold packed integer values
     * @param blocksOffset the offset where to start reading blocks
     * @param values the values buffer
     * @param valuesOffset the offset where to start writing values
     * @param iterations controls how much data to decode
     */
    void decode(byte[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations);

    /**
     * Read <code>iterations * blockCount()</code> blocks from <code>blocks</code>, decode them and
     * write <code>iterations * valueCount()</code> values into <code>values</code>.
     *
     * @param blocks the long blocks that hold packed integer values
     * @param blocksOffset the offset where to start reading blocks
     * @param values the values buffer
     * @param valuesOffset the offset where to start writing values
     * @param iterations controls how much data to decode
     */
    void decode(long[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations);

    /**
     * Read <code>8 * iterations * blockCount()</code> blocks from <code>blocks</code>, decode them
     * and write <code>iterations * valueCount()</code> values into <code>values</code>.
     *
     * @param blocks the long blocks that hold packed integer values
     * @param blocksOffset the offset where to start reading blocks
     * @param values the values buffer
     * @param valuesOffset the offset where to start writing values
     * @param iterations controls how much data to decode
     */
    void decode(byte[] blocks, int blocksOffset, int[] values, int valuesOffset, int iterations);
  }

  /** An encoder for packed integers. */
  public interface Encoder {

    /**
     * The minimum number of long blocks to encode in a single iteration, when using long encoding.
     */
    int longBlockCount();

    /** The number of values that can be stored in {@link #longBlockCount()} long blocks. */
    int longValueCount();

    /**
     * The minimum number of byte blocks to encode in a single iteration, when using byte encoding.
     */
    int byteBlockCount();

    /** The number of values that can be stored in {@link #byteBlockCount()} byte blocks. */
    int byteValueCount();

    /**
     * Read <code>iterations * valueCount()</code> values from <code>values</code>, encode them and
     * write <code>iterations * blockCount()</code> blocks into <code>blocks</code>.
     *
     * @param blocks the long blocks that hold packed integer values
     * @param blocksOffset the offset where to start writing blocks
     * @param values the values buffer
     * @param valuesOffset the offset where to start reading values
     * @param iterations controls how much data to encode
     */
    void encode(long[] values, int valuesOffset, long[] blocks, int blocksOffset, int iterations);

    /**
     * Read <code>iterations * valueCount()</code> values from <code>values</code>, encode them and
     * write <code>8 * iterations * blockCount()</code> blocks into <code>blocks</code>.
     *
     * @param blocks the long blocks that hold packed integer values
     * @param blocksOffset the offset where to start writing blocks
     * @param values the values buffer
     * @param valuesOffset the offset where to start reading values
     * @param iterations controls how much data to encode
     */
    void encode(long[] values, int valuesOffset, byte[] blocks, int blocksOffset, int iterations);

    /**
     * Read <code>iterations * valueCount()</code> values from <code>values</code>, encode them and
     * write <code>iterations * blockCount()</code> blocks into <code>blocks</code>.
     *
     * @param blocks the long blocks that hold packed integer values
     * @param blocksOffset the offset where to start writing blocks
     * @param values the values buffer
     * @param valuesOffset the offset where to start reading values
     * @param iterations controls how much data to encode
     */
    void encode(int[] values, int valuesOffset, long[] blocks, int blocksOffset, int iterations);

    /**
     * Read <code>iterations * valueCount()</code> values from <code>values</code>, encode them and
     * write <code>8 * iterations * blockCount()</code> blocks into <code>blocks</code>.
     *
     * @param blocks the long blocks that hold packed integer values
     * @param blocksOffset the offset where to start writing blocks
     * @param values the values buffer
     * @param valuesOffset the offset where to start reading values
     * @param iterations controls how much data to encode
     */
    void encode(int[] values, int valuesOffset, byte[] blocks, int blocksOffset, int iterations);
  }

  /**
   * A read-only random access array of positive integers.
   *
   * @lucene.internal
   */
  public abstract static class Reader implements Accountable {

    /** Get the long at the given index. Behavior is undefined for out-of-range indices. */
    public abstract long get(int index);

    /**
     * Bulk get: read at least one and at most <code>len</code> longs starting from <code>index
     * </code> into <code>arr[off:off+len]</code> and return the actual number of values that have
     * been read.
     */
    public int get(int index, long[] arr, int off, int len) {
      assert len > 0 : "len must be > 0 (got " + len + ")";
      assert index >= 0 && index < size();
      assert off + len <= arr.length;

      final int gets = Math.min(size() - index, len);
      for (int i = index, o = off, end = index + gets; i < end; ++i, ++o) {
        arr[o] = get(i);
      }
      return gets;
    }

    /**
     * @return the number of values.
     */
    public abstract int size();
  }

  /** Run-once iterator interface, to decode previously saved PackedInts. */
  public interface ReaderIterator {
    /** Returns next value */
    long next() throws IOException;

    /**
     * Returns at least 1 and at most <code>count</code> next values, the returned ref MUST NOT be
     * modified
     */
    LongsRef next(int count) throws IOException;

    /** Returns number of bits per value */
    int getBitsPerValue();

    /** Returns number of values */
    int size();

    /** Returns the current position */
    int ord();
  }

  abstract static class ReaderIteratorImpl implements ReaderIterator {

    protected final DataInput in;
    protected final int bitsPerValue;
    protected final int valueCount;

    protected ReaderIteratorImpl(int valueCount, int bitsPerValue, DataInput in) {
      this.in = in;
      this.bitsPerValue = bitsPerValue;
      this.valueCount = valueCount;
    }

    @Override
    public long next() throws IOException {
      LongsRef nextValues = next(1);
      assert nextValues.length > 0;
      final long result = nextValues.longs[nextValues.offset];
      ++nextValues.offset;
      --nextValues.length;
      return result;
    }

    @Override
    public int getBitsPerValue() {
      return bitsPerValue;
    }

    @Override
    public int size() {
      return valueCount;
    }
  }

  /**
   * A packed integer array that can be modified.
   *
   * @lucene.internal
   */
  public abstract static class Mutable extends Reader {

    /**
     * @return the number of bits used to store any given value. Note: This does not imply that
     *     memory usage is {@code bitsPerValue * #values} as implementations are free to use
     *     non-space-optimal packing of bits.
     */
    public abstract int getBitsPerValue();

    /**
     * Set the value at the given index in the array.
     *
     * @param index where the value should be positioned.
     * @param value a value conforming to the constraints set by the array.
     */
    public abstract void set(int index, long value);

    /**
     * Bulk set: set at least one and at most <code>len</code> longs starting at <code>off</code> in
     * <code>arr</code> into this mutable, starting at <code>index</code>. Returns the actual number
     * of values that have been set.
     */
    public int set(int index, long[] arr, int off, int len) {
      assert len > 0 : "len must be > 0 (got " + len + ")";
      assert index >= 0 && index < size();
      len = Math.min(len, size() - index);
      assert off + len <= arr.length;

      for (int i = index, o = off, end = index + len; i < end; ++i, ++o) {
        set(i, arr[o]);
      }
      return len;
    }

    /**
     * Fill the mutable from <code>fromIndex</code> (inclusive) to <code>toIndex</code> (exclusive)
     * with <code>val</code>.
     */
    public void fill(int fromIndex, int toIndex, long val) {
      assert val <= maxValue(getBitsPerValue());
      assert fromIndex <= toIndex;
      for (int i = fromIndex; i < toIndex; ++i) {
        set(i, val);
      }
    }

    /** Sets all values to 0. */
    public void clear() {
      fill(0, size(), 0);
    }
  }

  /**
   * A simple base for Readers that keeps track of valueCount and bitsPerValue.
   *
   * @lucene.internal
   */
  abstract static class ReaderImpl extends Reader {
    protected final int valueCount;

    protected ReaderImpl(int valueCount) {
      this.valueCount = valueCount;
    }

    @Override
    public abstract long get(int index);

    @Override
    public final int size() {
      return valueCount;
    }
  }

  abstract static class MutableImpl extends Mutable {

    protected final int valueCount;
    protected final int bitsPerValue;

    protected MutableImpl(int valueCount, int bitsPerValue) {
      this.valueCount = valueCount;
      assert bitsPerValue > 0 && bitsPerValue <= 64 : "bitsPerValue=" + bitsPerValue;
      this.bitsPerValue = bitsPerValue;
    }

    @Override
    public final int getBitsPerValue() {
      return bitsPerValue;
    }

    @Override
    public final int size() {
      return valueCount;
    }

    @Override
    public String toString() {
      return getClass().getSimpleName()
          + "(valueCount="
          + valueCount
          + ",bitsPerValue="
          + bitsPerValue
          + ")";
    }
  }

  /** A {@link Reader} which has all its values equal to 0 (bitsPerValue = 0). */
  public static final class NullReader extends Reader {

    private static final NullReader DEFAULT_PACKED_LONG_VALUES_PAGE_SIZE =
        new NullReader(PackedLongValues.DEFAULT_PAGE_SIZE);

    private final int valueCount;

    public static NullReader forCount(int valueCount) {
      if (valueCount == PackedLongValues.DEFAULT_PAGE_SIZE) {
        return DEFAULT_PACKED_LONG_VALUES_PAGE_SIZE;
      }
      return new NullReader(valueCount);
    }

    /** Sole constructor. */
    private NullReader(int valueCount) {
      this.valueCount = valueCount;
    }

    @Override
    public long get(int index) {
      return 0;
    }

    @Override
    public int get(int index, long[] arr, int off, int len) {
      assert len > 0 : "len must be > 0 (got " + len + ")";
      assert index >= 0 && index < valueCount;
      len = Math.min(len, valueCount - index);
      Arrays.fill(arr, off, off + len, 0);
      return len;
    }

    @Override
    public int size() {
      return valueCount;
    }

    @Override
    public long ramBytesUsed() {
      return valueCount == PackedLongValues.DEFAULT_PAGE_SIZE
          ? 0
          : RamUsageEstimator.alignObjectSize(
              RamUsageEstimator.NUM_BYTES_OBJECT_HEADER + Integer.BYTES);
    }
  }

  /**
   * A write-once Writer.
   *
   * @lucene.internal
   */
  public abstract static class Writer {
    protected final DataOutput out;
    protected final int valueCount;
    protected final int bitsPerValue;

    protected Writer(DataOutput out, int valueCount, int bitsPerValue) {
      assert bitsPerValue <= 64;
      assert valueCount >= 0 || valueCount == -1;
      this.out = out;
      this.valueCount = valueCount;
      this.bitsPerValue = bitsPerValue;
    }

    /** The format used to serialize values. */
    protected abstract PackedInts.Format getFormat();

    /** Add a value to the stream. */
    public abstract void add(long v) throws IOException;

    /** The number of bits per value. */
    public final int bitsPerValue() {
      return bitsPerValue;
    }

    /** Perform end-of-stream operations. */
    public abstract void finish() throws IOException;

    /**
     * Returns the current ord in the stream (number of values that have been written so far minus
     * one).
     */
    public abstract int ord();
  }

  /**
   * Get a {@link Decoder}.
   *
   * @param format the format used to store packed ints
   * @param version the compatibility version
   * @param bitsPerValue the number of bits per value
   * @return a decoder
   */
  public static Decoder getDecoder(Format format, int version, int bitsPerValue) {
    checkVersion(version);
    return BulkOperation.of(format, bitsPerValue);
  }

  /**
   * Get an {@link Encoder}.
   *
   * @param format the format used to store packed ints
   * @param version the compatibility version
   * @param bitsPerValue the number of bits per value
   * @return an encoder
   */
  public static Encoder getEncoder(Format format, int version, int bitsPerValue) {
    checkVersion(version);
    return BulkOperation.of(format, bitsPerValue);
  }

  /**
   * Expert: Restore a {@link ReaderIterator} from a stream without reading metadata at the
   * beginning of the stream. This method is useful to restore data from streams which have been
   * created using {@link PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)}.
   *
   * @param in the stream to read data from, positioned at the beginning of the packed values
   * @param format the format used to serialize
   * @param version the version used to serialize the data
   * @param valueCount how many values the stream holds
   * @param bitsPerValue the number of bits per value
   * @param mem how much memory the iterator is allowed to use to read-ahead (likely to speed up
   *     iteration)
   * @return a ReaderIterator
   * @see PackedInts#getWriterNoHeader(DataOutput, Format, int, int, int)
   * @lucene.internal
   */
  public static ReaderIterator getReaderIteratorNoHeader(
      DataInput in, Format format, int version, int valueCount, int bitsPerValue, int mem) {
    checkVersion(version);
    return new PackedReaderIterator(format, version, valueCount, bitsPerValue, in, mem);
  }

  /**
   * Create a packed integer array with the given amount of values initialized to 0. the valueCount
   * and the bitsPerValue cannot be changed after creation. All Mutables known by this factory are
   * kept fully in RAM.
   *
   * <p>Positive values of <code>acceptableOverheadRatio</code> will trade space for speed by
   * selecting a faster but potentially less memory-efficient implementation. An <code>
   * acceptableOverheadRatio</code> of {@link PackedInts#COMPACT} will make sure that the most
   * memory-efficient implementation is selected whereas {@link PackedInts#FASTEST} will make sure
   * that the fastest implementation is selected.
   *
   * @param valueCount the number of elements
   * @param bitsPerValue the number of bits available for any given value
   * @param acceptableOverheadRatio an acceptable overhead ratio per value
   * @return a mutable packed integer array
   * @lucene.internal
   */
  public static Mutable getMutable(
      int valueCount, int bitsPerValue, float acceptableOverheadRatio) {
    final FormatAndBits formatAndBits =
        fastestFormatAndBits(valueCount, bitsPerValue, acceptableOverheadRatio);
    return getMutable(valueCount, formatAndBits.bitsPerValue, formatAndBits.format);
  }

  /**
   * Same as {@link #getMutable(int, int, float)} with a pre-computed number of bits per value and
   * format.
   *
   * @lucene.internal
   */
  public static Mutable getMutable(int valueCount, int bitsPerValue, PackedInts.Format format) {
    assert valueCount >= 0;
    switch (format) {
      case PACKED_SINGLE_BLOCK:
        return Packed64SingleBlock.create(valueCount, bitsPerValue);
      case PACKED:
        return new Packed64(valueCount, bitsPerValue);
      default:
        throw new AssertionError();
    }
  }

  /**
   * Expert: Create a packed integer array writer for the given output, format, value count, and
   * number of bits per value.
   *
   * <p>The resulting stream will be long-aligned. This means that depending on the format which is
   * used, up to 63 bits will be wasted. An easy way to make sure that no space is lost is to always
   * use a <code>valueCount</code> that is a multiple of 64.
   *
   * <p>This method does not write any metadata to the stream, meaning that it is your
   * responsibility to store it somewhere else in order to be able to recover data from the stream
   * later on:
   *
   * <ul>
   *   <li><code>format</code> (using {@link Format#getId()}),
   *   <li><code>valueCount</code>,
   *   <li><code>bitsPerValue</code>,
   *   <li>{@link #VERSION_CURRENT}.
   * </ul>
   *
   * <p>It is possible to start writing values without knowing how many of them you are actually
   * going to write. To do this, just pass <code>-1</code> as <code>valueCount</code>. On the other
   * hand, for any positive value of <code>valueCount</code>, the returned writer will make sure
   * that you don't write more values than expected and pad the end of stream with zeros in case you
   * have written less than <code>valueCount</code> when calling {@link Writer#finish()}.
   *
   * <p>The <code>mem</code> parameter lets you control how much memory can be used to buffer
   * changes in memory before flushing to disk. High values of <code>mem</code> are likely to
   * improve throughput. On the other hand, if speed is not that important to you, a value of <code>
   * 0</code> will use as little memory as possible and should already offer reasonable throughput.
   *
   * @param out the data output
   * @param format the format to use to serialize the values
   * @param valueCount the number of values
   * @param bitsPerValue the number of bits per value
   * @param mem how much memory (in bytes) can be used to speed up serialization
   * @return a Writer
   * @see PackedInts#getReaderIteratorNoHeader(DataInput, Format, int, int, int, int)
   * @lucene.internal
   */
  public static Writer getWriterNoHeader(
      DataOutput out, Format format, int valueCount, int bitsPerValue, int mem) {
    return new PackedWriter(format, out, valueCount, bitsPerValue, mem);
  }

  /**
   * Returns how many bits are required to hold values up to and including maxValue NOTE: This
   * method returns at least 1.
   *
   * @param maxValue the maximum value that should be representable.
   * @return the amount of bits needed to represent values from 0 to maxValue.
   * @lucene.internal
   */
  public static int bitsRequired(long maxValue) {
    if (maxValue < 0) {
      throw new IllegalArgumentException("maxValue must be non-negative (got: " + maxValue + ")");
    }
    return unsignedBitsRequired(maxValue);
  }

  /**
   * Returns how many bits are required to store <code>bits</code>, interpreted as an unsigned
   * value. NOTE: This method returns at least 1.
   *
   * @lucene.internal
   */
  public static int unsignedBitsRequired(long bits) {
    return Math.max(1, 64 - Long.numberOfLeadingZeros(bits));
  }

  /**
   * Returns how many bits are required to hold values up to and including maxValue NOTE: This
   * method returns at least 1.
   *
   * @param maxValue the maximum int value that should be representable.
   * @return the amount of bits needed to represent values from 0 to maxValue.
   * @lucene.internal
   */
  public static int bitsRequired(int maxValue) {
    if (maxValue < 0) {
      throw new IllegalArgumentException("maxValue must be non-negative (got: " + maxValue + ")");
    }
    return unsignedBitsRequired(maxValue);
  }

  /**
   * Returns how many bits are required to store <code>bits</code>, interpreted as an unsigned
   * value. NOTE: This method returns at least 1.
   *
   * @param bits the int value to be stored, interpreted as unsigned.
   * @return the amount of bits needed to represent the unsigned value.
   * @lucene.internal
   */
  public static int unsignedBitsRequired(int bits) {
    return Math.max(1, 32 - Integer.numberOfLeadingZeros(bits));
  }

  /**
   * Calculates the maximum unsigned long that can be expressed with the given number of bits.
   *
   * @param bitsPerValue the number of bits available for any given value.
   * @return the maximum value for the given bits.
   * @lucene.internal
   */
  public static long maxValue(int bitsPerValue) {
    return bitsPerValue == 64 ? Long.MAX_VALUE : ~(~0L << bitsPerValue);
  }

  /**
   * Copy <code>src[srcPos:srcPos+len]</code> into <code>dest[destPos:destPos+len]</code> using at
   * most <code>mem</code> bytes.
   */
  public static void copy(Reader src, int srcPos, Mutable dest, int destPos, int len, int mem) {
    assert srcPos + len <= src.size();
    assert destPos + len <= dest.size();
    final int capacity = mem >>> 3;
    if (capacity == 0) {
      for (int i = 0; i < len; ++i) {
        dest.set(destPos++, src.get(srcPos++));
      }
    } else if (len > 0) {
      // use bulk operations
      final long[] buf = new long[Math.min(capacity, len)];
      copy(src, srcPos, dest, destPos, len, buf);
    }
  }

  /**
   * Same as {@link #copy(Reader, int, Mutable, int, int, int)} but using a pre-allocated buffer.
   */
  static void copy(Reader src, int srcPos, Mutable dest, int destPos, int len, long[] buf) {
    assert buf.length > 0;
    int remaining = 0;
    while (len > 0) {
      final int read = src.get(srcPos, buf, remaining, Math.min(len, buf.length - remaining));
      assert read > 0;
      srcPos += read;
      len -= read;
      remaining += read;
      final int written = dest.set(destPos, buf, 0, remaining);
      assert written > 0;
      destPos += written;
      if (written < remaining) {
        System.arraycopy(buf, written, buf, 0, remaining - written);
      }
      remaining -= written;
    }
    while (remaining > 0) {
      final int written = dest.set(destPos, buf, 0, remaining);
      destPos += written;
      remaining -= written;
      System.arraycopy(buf, written, buf, 0, remaining);
    }
  }

  /**
   * Check that the block size is a power of 2, in the right bounds, and return its log in base 2.
   */
  static int checkBlockSize(int blockSize, int minBlockSize, int maxBlockSize) {
    if (blockSize < minBlockSize || blockSize > maxBlockSize) {
      throw new IllegalArgumentException(
          "blockSize must be >= "
              + minBlockSize
              + " and <= "
              + maxBlockSize
              + ", got "
              + blockSize);
    }
    if ((blockSize & (blockSize - 1)) != 0) {
      throw new IllegalArgumentException("blockSize must be a power of two, got " + blockSize);
    }
    return Integer.numberOfTrailingZeros(blockSize);
  }

  /**
   * Return the number of blocks required to store <code>size</code> values on <code>blockSize
   * </code>.
   */
  static int numBlocks(long size, int blockSize) {
    final int numBlocks = (int) (size / blockSize) + (size % blockSize == 0 ? 0 : 1);
    if ((long) numBlocks * blockSize < size) {
      throw new IllegalArgumentException("size is too large for this block size");
    }
    return numBlocks;
  }
}
